300 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如， [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

** 输入：**nums = [10,9,2,5,3,7,101,18] ** 输出：**4 ** 解释：** 最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

** 输入：**nums = [0,1,0,3,2,3] ** 输出：**4

示例 3：

** 输入：**nums = [7,7,7,7,7,7,7] ** 输出：**1

动态规划记忆化搜索从后往前找找到比后一个数小的最大的那个

var lengthOfLIS = function(nums) {
    const memo = [];

    function dfs(i) {
        if (memo[i] !== undefined) return memo[i]; // 检查是否已缓存
        let res = 0;
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                res = Math.max(res, dfs(j));
            }
        }
        const result = res + 1;
        memo[i] = result; // 存储到数组
        return result;
    }

    let maxLen = 0;
    for (let i = 0; i < nums.length; i++) {
        maxLen = Math.max(maxLen, dfs(i));
    }
    return maxLen;
};

改成递推

function lengthOfLIS(nums) {
    if (nums.length === 0) return 0;
    const f = new Array(nums.length).fill(0); // 初始化f数组
    
    for (let i = 0; i < nums.length; i++) {
        // 初始时，最长递增子序列至少包含自己（长度为1）
        f[i] = 1; // 直接初始化为1（替代原来的+=1）
        // 检查所有前面的元素
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                f[i] = Math.max(f[i], f[j] + 1); // 更新最大值
            }
        }
    }
    return Math.max(...f); // 取f数组中的最大值
}

贪心 + 二分维护一个数组单调递增数组 g 每次遍历出的东西往 g 里加定义 g [i] 表示长为 i+1 的上升子序列的末尾元素的最小值。一次只能添加或修改一个值添加就是比最末尾大加到最末尾修改就是比最末尾小查找比他小的最大值修改那个放进去过程中的 g 不是答案之后过程结束才是答案

function lengthOfLIS(nums) {
    const g = [];
    
    // 实现 bisect_left 等效功能
    const bisectLeft = (arr, target) => {
        let low = 0;
        let high = arr.length;
        while (low < high) {
            const mid = (low + high) >>> 1; // 无符号右移等价于 Math.floor((low + high)/2)
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    };

    for (const x of nums) {
        const j = bisectLeft(g, x);
        if (j === g.length) { // 当x是当前最大元素时
            g.push(x);
        } else {
            g[j] = x;
        }
    }
    return g.length;
}

300 最长递增子序列 ​

300 最长递增子序列